148

12

Systems and Networks

A simple algorithm for generating scale-free networks was developed by Albert

and Barabási (2002): Start with a small numberm 0m0 of nodes and add, stepwise, new

nodes with m left parenthesis less than or equals m 0 right parenthesism(≤m0) edges, linking each new node to mm existing nodes. Unlike the

random addition of edges that would result in an Erd˝os–Rényi graph, the nodes are

preferentially attached to already well-connected nodes; that is, the probability that

a new node will be connected to existing node ii is

upper P left parenthesis k Subscript i Baseline right parenthesis equals k Subscript i Baseline divided by sigma summation Underscript j Endscripts k Subscript j Baseline periodP(ki) = ki/

Σ

j

k j .

(12.17)

Aftertt steps, one hasm 0 plus tm0 + t nodes andm tmt edges, and the exponentgammaγ appears (from

numerical simulations) to be 3.

The average degree of this network remains constant as it grows. Empirical studies

have shown, however, that in many natural systems, the average degree increases with

growth (this phenomenon is called “accelerated growth”); in other words, each new

node is connected to a fixed fraction of the existing nodes. In this case, upper E tilde upper N squaredE ∼N ².

If nodes are removed randomly, an Erd˝os–Rényi network will break up into sev-

eral disconnected networks, whereas a scale-free network is not much affected. On

the other hand, an Erd˝os–Rényi network is fairly robust with respect to targeted

removal, whereas a scale-free network quickly breaks up if the hubs—highly con-

nected nodes—are targeted.

The simple SIR model of the spreading of an epidemic (see Chap. 20) neglects

the possibility that an infectious agent may propagate on a network, with rate lamda equals nu divided by deltaλ =

ν/δ, where susceptible nodes are infected with rate nuν if connected to an infected

node, and are cured with rate deltaδ, reverting to the susceptible state. On regular and

random networks there is a nonzero thresholdlamda Subscript cλc, below which an infection dies away

exponentially, and above which it becomes persistent. But the threshold is zero on a

scale-free network. ¹⁴

Network techniques allow graphical approaches to chemical reaction kinetics to

be simplified. ¹⁵ This is especially valuable when dealing with complex biological

systems.

12.2.1

Trees

A tree is a graph in which each pair of vertices is joined by a unique edge; there is

exactly one more vertex than the number of edges. In a binary tree, each vertex has

either one or three edges connected to it. A rooted tree has one particular node called

the root (corresponding to the point at which the trunk of a real (biological) tree

emerges from the ground). Trees represent ultrametric space satisfying the strong

triangle inequality

d left parenthesis x comma z right parenthesis less than or equals max left brace d left parenthesis x comma y right parenthesis comma d left parenthesis y comma z right parenthesis right brace commad(x, z) ≤max{d(x, y), d(y, z)} ,

(12.18)

14 Pastor-Satorras and Vespignani (2001); see Dorogovtsev et al. (2008) for extensive discussion.

15 Peusner et al. (1985).